package leetcode.双指针法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 四数之和
 *
 * 三数之和需要三个指针，四数之和需要四个指针
 * 三个指针需要最后面的两个频繁移动、四个指针需要最后面的三个频繁移动
 *
 * 解题思路完全与之前的三数之和一样，
 *      唯一要注意的就是去重的策略：去重不是跳过重复存在的数字，而是指向重复数字的最后一个
 * 然后还要增加一个J循环 也就是先固定i、j，然后让l、和k指针不断变化，
 *      当不满足l < k的时候让j++，当不满足j <= nums.length-2的时候，让i++，
 *      i结束的标志是i < nums.length -3
 */
public class Test18四数之和 {

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums.length < 4) {
            return ans;
        }
        Arrays.sort(nums);
        // 从第一个数开始遍历
        for (int i = 0; i < nums.length -3 ; i++) {
            // 每次重置i的时候，重置j、k、l
            int j = i + 1;
            int k = nums.length - 1;
            int l = j + 1;
            for (; j <= nums.length - 2; j++) {
                // 重置j也要重置l、k
                l = j + 1;
                k = nums.length - 1;
                while (l < k) {
                    int result = nums[i] + nums[j] + nums[l] + nums[k];
                    if (result == target) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[l]);
                        list.add(nums[k]);
                        ans.add(list);
                        // 去重
                        while (l < k && nums[l] == nums[l + 1]) {
                            l++;
                        }
                        l++;
                    } else if (result < target) {
                        while (l < k && nums[l] == nums[l + 1]) {
                            l++;
                        }
                        l++;
                    } else {
                        while (l < k && nums[k] == nums[k - 1]) {
                            k--;
                        }
                        k--;
                    }
                }
                while (j < nums.length - 2 && nums[j] == nums[j + 1]) {
                    j++;
                }
            }
            while (i < nums.length - 3 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
//        int[] nums = new int[] {1, 0, -1, 0, -2, 2};
//        int[] nums = new int[] {0,0,0,0};
//        int[] nums = new int[] {-3,-2,-1,0,0,1,2,3};
//        int[] nums = new int[] {-1,-5,-5,-3,2,5,0,4};

        int[] nums = new int[]{0, 3, 4, -2, -1, 3, 3, 3, 1};
        System.out.println(fourSum(nums, 2));
    }

}
